﻿#include <iostream>

using namespace std;

void printfArray(int *array, int length) {
    for (int i = 0; i < length; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void shellSort(int *array, int length) {
    for (int gap = length / 2; gap >= 1; gap /= 2) {
        for (int i = gap; i < length; i++) {
            int j = i;
            int current = array[i];
            while (0 <= j - gap && current < array[j - gap]) {
                array[j] = array[j - gap];
                j -= gap;
            }
            array[j] = current;
        }
    }
}

int main() {
    int array[] = {2, 4, 6, 7, 3, 2, 5, 6, 7, 2, 2, 4, 2, 1, 4, 1, 6, 7, 9, 0, 8};
    int length = (sizeof(array) / sizeof(int));
    cout << "length = " << length << endl;

    cout << "排序前: ";
    printfArray(array, length);

    shellSort(array, length);

    cout << "排序后: ";
    printfArray(array, length);

    return 0;
}